package lrucache;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName MyLRUCache
 * @Description 手写 LRU，支持泛型键和值
 * @Author ZJX
 * @Date 2024/9/8 11:30
 * @Version 1.0
 */
public class MyLRUCache<K, V> {

    static class DoublyLinkedListNode<K, V> {
        K key;    // 泛型键
        V value;  // 泛型值
        DoublyLinkedListNode<K, V> prior;  // 前驱节点
        DoublyLinkedListNode<K, V> next;  // 后继节点

        public DoublyLinkedListNode() {}

        public DoublyLinkedListNode(K key, V value){
            this.key = key;
            this.value = value;
        }
    }

    private DoublyLinkedListNode<K, V> head; // 头节点
    private DoublyLinkedListNode<K, V> tail; // 尾结点

    // 哈希表，用于 O(1) 时间内查找缓存的值
    private Map<K, DoublyLinkedListNode<K, V>> cache = new HashMap<>();

    // 缓存的最大容量
    private int capacity;

    public MyLRUCache(int capacity) {
        this.capacity = capacity;
        head = new DoublyLinkedListNode<>(); // 虚拟头节点
        tail = new DoublyLinkedListNode<>(); // 虚拟尾节点
        head.next = tail;
        tail.prior = head;
    }

    public V get(K key) {
        DoublyLinkedListNode<K, V> node = cache.get(key);
        if (node == null) {
            // 说明键不存在
            return null;
        }
        // 如果键存在，将其移动到尾部 (最新使用)
        moveToTail(node);
        return node.value;
    }

    // 链表头部保存的是最久未使用的节点，尾部保存的是最近使用的节点。
    public void put(K key, V value) {
        DoublyLinkedListNode<K, V> node = cache.get(key);
        // 1. 如果找到，更新value值，并将其放到尾部
        // 2. 如果没找到，添加此元素到尾部，检查 capacity，如果超过大小则移除头部元素
        if (node == null) {
            // 说明没存储过，添加此元素到尾部
            DoublyLinkedListNode<K, V> newNode = new DoublyLinkedListNode<>(key, value);
            cache.put(key, newNode);
            addToTail(newNode);

            // 如果超过容量，移除最久未使用的节点
            if (cache.size() > capacity) {
                DoublyLinkedListNode<K, V> oldest = head.next;
                removeNode(oldest);  // 头节点就是最久未使用的
                cache.remove(oldest.key);
            }
        } else {
            // 说明存储过，更新value值，并将其放到尾部
            node.value = value;
            moveToTail(node);
        }
    }

    // 双向链表中移除 node 节点
    private void removeNode(DoublyLinkedListNode<K, V> node) {
        node.prior.next = node.next;
        node.next.prior = node.prior;
    }

    // 将节点添加到链表尾部
    private void addToTail(DoublyLinkedListNode<K, V> node) {
        // 1. 将新节点的 prior 指向当前的尾部节点的前一个节点（tail.prior）
        node.prior = tail.prior;

        // 2. 将新节点的 next 指向尾部虚拟节点 tail
        node.next = tail;

        // 3. 将原尾部节点的 next 指向新节点
        tail.prior.next = node;

        // 4. 更新 tail.prior，使其指向新节点
        tail.prior = node;
    }

    // 将节点移到链表尾部
    private void moveToTail(DoublyLinkedListNode<K, V> node) {
        // 先移除节点，再添加到尾部
        removeNode(node);
        addToTail(node);
    }

    public static void main(String[] args) {
        MyLRUCache<Integer, String> cache = new MyLRUCache<>(2);

        cache.put(1, "A");
        cache.put(2, "B");
        System.out.println(cache.get(1));  // 返回 A
        cache.put(3, "C");                 // 移除键 2
        System.out.println(cache.get(2));  // 返回 null (未找到)
        cache.put(4, "D");                 // 移除键 1
        System.out.println(cache.get(1));  // 返回 null (未找到)
        System.out.println(cache.get(3));  // 返回 C
        System.out.println(cache.get(4));  // 返回 D
    }
}
